package search;


import java.util.Arrays;

/**
 * 斐波拉契查找
 */
public class FibonaciSearch {
    public static int maxSize = 20;
    public static void main(String[] args) {

        int[] arr = {1,8,10,89,1000,1234};
//        System.out.println(Arrays.toString(fib()));
    }

    //后面我们的mid = low+F(k-1)-1;需要用到斐波拉契数列
    //得到一个斐波拉契数列
    public static int[] fib(){
        int[] f = new int[20];
        f[0] = 1;
        f[1] = 1;
        for (int i = 2; i <maxSize ; i++) {
            f[i] = f[i-1] + f[i-2];
        }
        return f;
    }

    //斐波拉契查找算法

    /**
     *
     * @param a 数组
     * @param key 需要查找数
     * @return 返回对应下标，若没有返回-1
     */
    public static int fibSearch(int[] a, int key){
        int low = 0;
        int high = a.length-1;
        int k = 0; //斐波拉契分割数值的下标
        int mid = 0; //存放mid值
        int f[] = fib();  //得到斐波拉契数列
        //获取到斐波拉契分割数值的下标
        while (high > f[k] -1){
            k++;
        }
        //因为f[k]可能大于数组的长度，因此我们需要使用
        //Arrays类，构建一个新的数组并且指向a[]
//        int[] temp = Arrays.copyOf(a,f[k]);
        //
        return 0;
    }
}
